package com.eron.algorithm.array;

/**
 * 爬楼梯
 * 
 * https://leetcode-cn.com/problems/climbing-stairs/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china
 * 
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * 
 * 注意：给定 n 是一个正整数。
 * 
 * 示例 1：
 * 
 * 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 示例 2：
 * 
 * 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
 * 
 * 1. 能不能暴力解题
 * 
 * 2. 最基本的情况怎么解决
 * 
 * 3. 找最近重复子问题
 * 
 */
public class ClimbStairs {

    private static final String TAG = "ClimbStairs_result------>:";

    public static void main(String[] args) {

        int n = 30;
        System.out.println(TAG + climbStairs(n));
        System.out.println(TAG + climbStairs2(n));

    }

    /**
     * 斐波那契数列 f(n) = f(n-1)+f(n-2)
     * 
     * 1：1
     * 
     * 2：2
     * 
     * 3：f(1)+f(2)
     * 
     * 4：f(2)+f(3)
     * 
     * ****** 找 最近 重复子问题 ******
     * 
     * 
     * @param n
     * @return
     */
    private static int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int f1 = 1, f2 = 2, f3 = 3;
        for (int i = 3; i < n + 1; i++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }

    /**
     * leetcode 官方题解
     * 
     * @param n
     * @return
     */
    public static int climbStairs2(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
}
